//BST O(logn)
/*treap
每个节点有一个随机的额外权值
并且满足小根堆的性质
维护通过旋转实现——>右旋、左旋
只会发生父子改变关系以满足平衡树、小根堆性质
插入时首先按满足平衡树，再根据堆的性质旋转，
左儿子右旋，右儿子左旋,旋转后中序遍历不变
如：
		5,1
	3,4       8,3
1,10  4,5
	插入2,2
	变为
		5,1
	3,4       8,3
1,10  4,5
  2,2
  左旋
  		5,1
	3,4       8,3
2,2   4,5
 1,10
 右旋
 		5,1
 	2,2      8,3
 1,10  3,4
        4,5
*/
//自适应无需判断左旋/右旋
void rotate(int x)
{
    int y=dad[x],z=dad[y];
    bool f=s[1][y]==x;
    if(!is_root(y))s[s[1][z]==y][z]=x;
    s[f][y]=s[!f][x];
    s[!f][x]=y;
    dad[x]=z;
    dad[y]=x;
    dad[s[f][y]]=y;
    update(x);
    update(y);
}
//右旋
void r_rotate(int p)
{
	int q=dad[p],s=dad[q];
	int b=rs[p];	//右儿子
	ls[q]=t;	//Q左儿子变p
	dad[b]=q;	//改父亲
	dad[q]=p;
	dad[p]=s;
	rs[p]=q;
	if(ls[s]==q)
		ls[s]=p;
	else
		rs[s]=p;
}
//左旋
void l_rotate(int p)
{
	int q=dad[p],s=dad[q],t=ls[p];
	rs[q]=t;
	ls[p]=q;
	dad[p]=s;
	dad[q]=p;
	dad[t]=q;
	if(ls[s]==q)
		ls[s]=p;
	else
		rs[s]=p;
}
//无dad版
void r_rotate2(int &q,int p)	//q为p的父亲
{
	ls[q]=rs[p];
	rs[p]=q;
	q=p;	
}
void l_rotate2(int &q,int p)
{
	rs[q]=ls[p];
	ls[p]=q;
	q=p;
}

void add(int x,int &cur)	//cur为节点编号
{
	//V[]:权值
	//R[]:随机值
	if(!cur)	//插入节点
	{
		cur=++cnt;//节点编号
		V[cnt]=x;
		R[cnt]=rand();
		return;
	}
	if(x>V[cur])
	{
		add(x,ls[cur]);	//寻找在哪插入，向右儿子
		if(R[rs[cur]]<R[cur]) //旋转
			l_rotate(cur,rs[cur]);
	}else
	{
		add(x,ls[cur]);//向左儿子
		if(R[ls[cur]]<R[cur])//旋转
			r_rotate(cur,ls[cue])
	}
}
void del(int x,int &cur)
{
	if(V[cur]==x)	//删除一个权值为x的点
	{
		if(!ls[cur]||rs[xur])
		{
			cur=ls[cur]|rs[cur];//合并左右子树以删除
			return;
		}
		if(R[ls[cur]]>R[rs[cur]])//旋转至只有一个儿子
		{
			l_rotate2(cur,rs[cur]);
			del(x,ls[cur]);
		}else
		{
			r_rotate2(cur,ls[cur]);
			del(x,rs[cur]);
		}
	}else
		if(x<V[cur])
			del(x,ls[cur]);
		else 
			del(x,rs[cur]);
}